package xiaomin.demo.algorithm;

import javafx.animation.KeyValue;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;
/*
给定 一个 整型 数组， 找出 最大 下标 距离 j- i， 当 且 仅 当 A[ i]< A[ j] 和 i< j。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 65). 电子工业出版社. Kindle 版本.

思路：
1.构建递减序列
2.从远到近遍历,计算距离，
 */
public class Lesson05 {
    public static void run(){
        //int[] a={5,3,4,0,1,4,6};//结果4
        int[] a={5,3,4,0,1,4,1};//结果4

        ArrayList<Integer> indexList=new ArrayList<Integer>();

        //构造递减序列
        int temp=a[0];
        indexList.add(0);
        for(int i=1;i<a.length;i++){
            if(a[i]<temp){
                indexList.add(i);
                temp=a[i];
            }
        }

        int maxDistance=0;

        //从右到左遍历每个射手
        int currentTragetIndex=indexList.size()-1;
        for(int i=a.length-1;i>0;i--){
            //跟当前靶子对比
            while(currentTragetIndex>=0 && a[i]>a[indexList.get(currentTragetIndex)]){

                maxDistance=Math.max(maxDistance,i-indexList.get(currentTragetIndex));
                currentTragetIndex--;
            }

            if(currentTragetIndex==0){
                System.out.println(a[i]);
                break;//如果是最后一个靶子，并且已经找到跟它最大距离的射手，直接完成
            }
        }


        // 递减序列遍历
//        for(int i=0;i<list.size();i++){
//            System.out.println(list.get(i).getKey());
//            int startIndex=0;
//            int endIndex=0;
//            //把整个序列分成N个区间 N=list.size()+1，每个区间的中间的数字肯定是比左边大
//            //计算区间范围
//            startIndex=list.get(i).getValue();
//            if(i==list.size()-1)//最后一个数字
//            {
//                endIndex=a.length;
//            }
//            else {
//                endIndex=list.get(i+1).getValue();
//            }
//            //计算区间范围内最大距离
//            for(int j=startIndex;j<endIndex;j++){
//                if(a[j]>a[startIndex]){
//                    maxDistance=Math.max(maxDistance,j-startIndex);
//                }
//            }
//        }

        System.out.println(maxDistance);
    }
}
